﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using ProjectEuler.Linq;

namespace ProjectEuler
{
    public class SieveOfEratosthenes : ICollection<Int32>
    {
        private readonly BitArray _bits;
        private readonly List<Int32> _done = new List<Int32>();

        private Int32? _count;

        public SieveOfEratosthenes(Int32 max)
        {
            _bits = new BitArray(max + 1, true);

            foreach (var prime in Integers.PrimesUnder500)
            {
                if (prime > max)
                {
                    break;
                }

                _done.Add(prime);
                MarkMultiples(prime);
            }
        }

        public void EnsureComputedUpTo(Int32 max)
        {
            if (max >= _bits.Length)
            {
                throw new ArgumentOutOfRangeException("max");
            }

            using (var sieve = CreateSieve())
            {
                while (sieve.MoveNext())
                {
                    if (sieve.Current >= max)
                    {
                        break;
                    }
                }
            }
        }

        public IEnumerator<Int32> GetEnumerator()
        {
            foreach (var prime in _done)
            {
                yield return prime;
            }

            using (var sieve = CreateSieve())
            {
                while (sieve.MoveNext())
                {
                    yield return sieve.Current;
                }
            }
        }

        public IEnumerable<Int32> CompositesOdd()
        {
            return Composites(6, 2, Numeric.IsOdd);
        }

        public IEnumerable<Int32> CompositesEven()
        {
            return Composites(4, 2, Numeric.IsEven);
        }

        public IEnumerable<Int32> Composites()
        {
            return Composites(4, 1, null);
        }

        private IEnumerable<Int32> Composites(Int32 first, Int32 increment, Predicate<Int32> test)
        {
            var last = first;

            foreach (var prime in this)
            {
                while (last < prime)
                {
                    yield return last;
                    last += increment;
                }

                last = prime + 1;

                if (test != null)
                {
                    while (!test(last))
                    {
                        last++;
                    }
                }
            }
        }

        public Boolean IsPrime(Int32 n)
        {
            if (n >= 2)
            {
                if (n >= _bits.Length)
                {
                    throw new ArgumentOutOfRangeException("n");
                }

                if (n > _done.Last())
                {
                    EnsureComputedUpTo(n);
                }

                return IsPrimeCore(n);
            }

            return false;
        }

        public void CopyTo(Int32[] array, Int32 arrayIndex)
        {
            if (array == null)
            {
                throw new ArgumentNullException("array");
            }

            foreach (var prime in this)
            {
                if (arrayIndex >= array.Length)
                {
                    break;
                }
    
                array[arrayIndex++] = prime;
            }
        }

        public Int32 Count
        {
            get
            {
                if (!_count.HasValue)
                {
                    var i = 0;
                    foreach (var item in this)
                    {
                        i++;
                    }
                    _count = i;
                }

                return _count.Value;
            }
        }

        private IEnumerator<Int32> CreateSieve()
        {
            var last = _done.Last();
            var prevSquare =  last + 1;

            while ((last * last) < _bits.Length)
            {
                MarkMultiples(last);

                var square = last * last;

                for (; prevSquare < square; prevSquare++)
                {
                    if (IsPrimeCore(prevSquare))
                    {
                        _done.Add(prevSquare);
                        yield return prevSquare;
                    }
                }

                do
                {
                    last++;
                }
                while (!_bits[last]);
            }

            for (; prevSquare < _bits.Length; prevSquare++)
            {
                if (IsPrimeCore(prevSquare))
                {
                    yield return prevSquare;
                }
            }
        }

        private void MarkMultiples(Int32 factor)
        {
            for (var mark = (factor + factor); mark < _bits.Length; mark += factor)
            {
                _bits[mark] = false;
            }
        }

        private Boolean IsPrimeCore(Int32 n)
        {
            return (_bits[n]);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        void ICollection<Int32>.Add(Int32 item)
        {
            throw new NotSupportedException();
        }

        void ICollection<Int32>.Clear()
        {
            throw new NotSupportedException();
        }

        Boolean ICollection<Int32>.Contains(Int32 item)
        {
            return IsPrime(item);
        }

        Boolean ICollection<Int32>.IsReadOnly
        {
            get { return true; }
        }

        Boolean ICollection<Int32>.Remove(Int32 item)
        {
            throw new NotSupportedException();
        }
    }
}
